Exploiting duality in summarization with deterministic guarantees
Panagiotis Karras
Dimitris Sacharidis
Nikos Mamoulis
Summarization is an important task in data mining. A major challenge over the past years has been the efficient construction of fixed-space synopses that provide a deterministic quality guarantee, often expressed in terms of a maximum-error metric. Histograms and several hierarchical techniques have been proposed for this problem. However, their time and/or space complexities remain impractically high and depend not only on the data set size <i>n</i>, but also on the space budget <i>B</i>. These handicaps stem from a requirement to tabulate all allocations of synopsis space to different regions of the data. In this paper we develop an alternative methodology that dispels these deficiencies, thanks to a fruitful application of the solution to the dual problem: given a maximum allowed error, determine the minimum-space synopsis that achieves it. Compared to the state-of-the-art, our histogram construction algorithm reduces time complexity by (at least) a <i>B</i>log<sup>2</sup><i>n</i> over log&#949;* factor and our hierarchical synopsis algorithm reduces the complexity by (at least) a factor of log<sup>2</sup><i>B</i> over log&#949;* + log<i>n</i> in time and <i>B</i>(1-log <i>B</i> over log <i>n</i>) in space, where &#949;* is the optimal error. These complexity advantages offer both a space-efficiency and a scalability that previous approaches lacked. We verify the benefits of our approach in practice by experimentation.
